﻿/*
题目: 验证二叉树的前序序列化

序列化二叉树的一种方法是使用 前序遍历 。当我们遇到一个非空节点时，我们可以记录下这个节点的值。如果它是一个空节点，我们可以使用一个标记值记录，例如 #。

https://leetcode.cn/problems/verify-preorder-serialization-of-a-binary-tree/description/
*/

#include <iostream>
#include <random>
#include <string>
#include <vector>
#include <list>
#include "TreeNode.hpp"
#include "ListNode.hpp"
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <functional>

using namespace std;

class Solution {
public:
#define EMPTY '1'
#define NUMBER '2'

    bool isValidSerialization(string preorder) {
        // 先预处理
        vector<char> vct;
        init(preorder, vct);
        if (vct[0] == EMPTY)  return vct.size() == 1;

        // 槽位判断法
        int degree = 1;
        for (int i = 0; i < vct.size(); i++) {
            if (degree <= 0)     return false;       // 度为负数

            if (vct[i] == NUMBER) {                 // 多了一个结点，度 + 1
                degree++;
            }
            else if (vct[i] == EMPTY) {             // 空结点，度 - 1
                degree--;
            }
        }

        return degree == 0;
    }

    void init(string& preorder, vector<char>& vct) {
        int i = 0;
        while (i < preorder.size()) {
            int it = preorder.find(',', i);
            if (it == std::string::npos) {
                it = preorder.size();
            }

            string item = preorder.substr(i, it - i);
            if (item == "#")    vct.push_back(EMPTY);
            else                vct.push_back(NUMBER);

            i = it + 1;
        }
    }
};
